The present invention relates generally to systems for performing arithmetic operations, and in particular, to a method and apparatus for expediting the evaluation of an expression commonly used in signal processing of convolutionally encoded information to combine metrics associated with state changes.
Perhaps even more than other types of communications, radio communication suffers from the irregularities of its transmission medium. Radio communication system designers must compensate for time dispersion, fading and other changes in radio channels which impact transmitted signals. Frequently, these irregularities cause random bit errors. One way in which random bit errors are combatted in radio communication systems is by convolutionally encoding the signals prior to transmission.
In a convolutional code, code digits generated by an encoder in a particular time unit depend not only on the data to be characterized by those bits, but also on the code digits in a previous span of time units. A convolutional decoder operates by manipulating candidate code sequences through shift registers and decoding each new bit by evaluating its probable value (e.g., 1 or 0) in view of previously received bits.
By predicating the encoding scheme of each bit on the values of other, earlier transmitted data bits, a decoder can correctly reconstruct received data sequences which, to an extent, include random bit errors.
This type of encoding can be referred to as polynomial encoding, where the polynomial describes the code relationship between previous bits and a current bit. Consider the encoder hardware illustrated as FIG.(a). Therein, encoded output of a bit depends upon the values of two previous bits and the current input bit. Specifically, a value of a current bit d.sub.n is added modulo-2 (i.e., exclusive OR'ed) with the value of a previous bit d.sub.n-1 at block 10. Then, the output of block 10 is added modulo-2 with the value of the bit prior to d.sub.n-2 at block 20 to provide an encoded output. This exemplary type of encoding can be described by the polynomial
______________________________________ d.sub.n-2 d.sub.n-1 d.sub.n E ______________________________________ 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 ______________________________________
A trellis diagram is a form of code tree that is helpful in illustrating how systems employing convolutional codes operate. The exemplary trellis diagram of FIG. 1(b) depicts coded output of the encoder of FIG. 1(a) for possible sequences of two digits wherein an initial value for d.sub.n-1 and d.sub.n-2 are zero. Accordingly, the depicted trellis diagram corresponds to an encoder having four states (i.e., 00, 01, 10, 11). The binary values that constitute these states correspond to the values of d.sub.n-2 and d.sub.n-1, respectively. The output E of the encoder is thus controlled by d.sub.n, d.sub.n-1, d.sub.n-2 and the generator polynomial. In the illustration of FIG. 1(b), the encoder output values E are given by the binary values depicted in the figure, each of which is associated with an arrow emanating from a node. The type of arrow indicates the value of d.sub.n (solid: d.sub.n =0, dotted d.sub.n =1) associated with each path through the trellis.
Consider the nodes encircled by line 30. At node 31, the current state remains 00. If d.sub.n =0 (solid arrow emanating from right side of node 31), then the encoder output is also zero and the state remains 00. This is in accordance with the top row of the logic table illustrated above. If, on the other hand, d.sub.n =1 (dotted arrow emanating from right side of node 31) then the encoder output E is 1 (as shown in the second row from the top of the logic table above) and a transition is made to state 01.
Next, consider node 32. At this node current state is 01 since d.sub.n =1 occurred as an input to this node from state 00. If the next d.sub.n =0 (solid arrow emanating from right side of node 32), then the encoder output is one and the state transitions to 10 (as shown by the third row from the top of the logic table). If, on the other hand, d.sub.n =1 (dotted arrow emanating from right side of node 31) then the encoder output E is zero (as shown in the fourth row from the top of the logic table above) and a transition is made to state 11.
Having encoded and transmitted a data sequence, the next task in, for example, a radiocommunication system is to receive and decode the signal. A common technique for enhancing the decoding of convolutionally encoded data is to use Viterbi's maximum likelihood algorithm. A maximum likelihood receiver operates by selecting a known bit sequence closest to a received bit sequence. Because 2.sup.k bit sequences are involved (k being the number of data bits within a frame) in an ordinary convolutional maximum likelihood receiver decoder, the system stores the 2.sup.k bit sequences for comparison with a received bit sequence. For a large value of k, this can be unwieldy. Viterbi simplified the maximum likelihood evaluation by noting that each of the states represented has only a finite number of possible predecessor states, and that only the path (e.g., through the trellis diagram) that agrees most with the received sequence (the minimum distance path) need be retained for each state. For the trellis diagram depicted in FIG. 1(b), this is noted by considering that for each of the four states (00, 01, 10 and 11) each has only two possible predecessor states. That is, each node can only be reached through two states (e.g., you can only reach the 00 state from a previous 00 state or from a 10 state). Viterbi recognized that the likelihood evaluation could be significantly enhanced by using this factor in assessing possible paths through a trellis diagram, or like table.
Each possible path, or combination of state transitions, has an associated likelihood, or probability, of being correct. The probability of any given transition is based on the value of a newly received value, in view of a succession of predecessor values. The transition probabilities are commonly referred to as metrics or bit metrics, and a succession of bit metrics are referred to as a path metric denoting the likelihood of a sequence of possible state transitions.
Consider an example wherein a data bit stream is encoded using a Viterbi convolutional encoder to generate an encoded bit stream. To introduce redundancy, two code generators are used to produce two separate code bit streams, each based on the same data bit stream. The two bit streams are interleaved and transmitted over a medium, e.g., an air interface, that renders the bit streams susceptible to random bit errors. At the receiver, the bit streams are received by a detector. The detector produces a pair of outputs: a detected binary value (e.g., 1 or 0); and a metric indicating the probability of the detected binary value being correct. This information is then deinterleaved and passed to a decoder for evaluation as described above. In the examples discussed herein, a lowest accumulated metric value indicates a high probability of correctness, however, those skilled in the art will be aware that other metric conventions can be used.
Consider a somewhat oversimplified example of a decoder having, for example, four states for processing the deinterleaved bit streams wherein each state corresponds to a proposed bit sequence. This decoding example is illustrated in FIG. 2 as a four state trellis. The selection of the correct proposed bit sequence depends on the accumulated metric associated with each path tested by the decoder. In this example, an accumulated path metric is generated for each bit received. Each bit received alters the assessment of the possible paths through the trellis. Hence, for each bit received, a metric associated with the decoder's level of certainty of the value, i.e., 0 or 1, of that bit is conditionally added to the accumulated path metric. For the example given above wherein two bit streams, each having an associated metric, are received, the capability to quickly and efficiently evaluate the various metric sums is desirable.
Evaluation of the accumulated path metric, in the context of performing the decoding process, requires repeated evaluation of the expression given by Equation (1): EQU x(n,m)=n*a+m*b (1)
where: a and b are metrics in the form of numerical constants (integer or floating point);
n and m are binary state integer variables; PA1 * corresponds to multiplication; and PA1 + corresponds to addition.
The values of a and b above represent the metric values corresponding to the first and second bit streams, respectively. The metrics, a and b, are used for assessing the probable correctness of the proposed received bit in the context of the various possible paths through the trellis. The addition of either or both of the metrics to the accumulated path metric is controlled by the binary integer state variables n and m. Output from Equation 1 is given by the following table which illustrates the usage of these metrics to indicate possible errors in the hypothesized bit streams.
TABLE 1 ______________________________________ 0 no bit errors in either bit stream a bit error in the first bit stream only b bit error in the second bit stream only a+b bit errors in both bit streams ______________________________________
A numerical example will aid the description. Suppose that a first bit, corresponding to a first bit in a bit stream encoded using a first polynomial, is detected as a logical "0" with a 70% certainty. A second bit, corresponding to the same original bit stream, albeit encoded at the transmitter with a different polynomial, is received by the detector, and determined to be a logical "1" with a 90% certainty. After deinterleaving, a decoder, e.g., a Viterbi decoder, will then evaluate the different paths available between the plurality of states used in the trellis. In this simplified example, there are four states and eight paths.
For example, with reference to FIG. 2, the decoder, operating on the first deinterleaved bit, will evaluate the hypothetical transition between states 00 and 00, i.e., testing a transition denoted by the topmost arrow 50 where the hypothesized bit is a logical "0" as indicated by the "0 " above arrow 50. Since the metric associated with this bit indicates that the received bit is believed to be a zero, the decoder will add zero, i.e., no bit error, for this bit stream to the accumulated metric. At the same time, the decoder, when operating on the second deinterleaved bit, will evaluate this state transition, however, with a different result. Since the transition indicates a hypothetical logical "0", and the received bit is believed to be a logical "1" with a 90% certainty level, the decoder will add 0.9 to the accumulated metric. Thus, this example can be described by the third row of Table 1 above.
In a conventional system, Equation (1) is evaluated by the circuit arrangement depicted in FIG. 3. In this arrangement, the multiplexors (MUXs) 301 and 303 will output either a zero or their respective constants (a and/or b) based on the binary input control signals n and m. Regardless of the output selection, the outputs of the MUXs are added together by adder 305 to produce an output x. The output x is then added to the accumulated metric associated with that path.
A problem with the arrangement of FIG. 3 is that, notwithstanding the ultimate output value x, the adder 305 is used for the evaluation of every path in the trellis. However, adders are relatively complex (and hence slower) as compared to other digital logic devices, for example multiplexors. Accordingly, use of the adder 305, in the conventional manner depicted in FIG. 3, slows the solution speed of the evaluation of Equation (1). It is desirable however, to be able to quickly and efficiently evaluate path metric, especially in view of present digital signal processing wherein high bit rates are commonly used to transmit and receive data.